package 排序算法;

/**
 * 归并排序：
 * 拆：把所有所有数据不断的拆分，拆到不能拆为止（元素个数为1）
 * 合：开始合并数据，从小到大开始两两合并
 */
public class 归并排序 {

    private static Integer[] leftArray;
    private static Integer[] arrays = {1, 56, 32, 56, 12, 77, 88, 21};

    public static void main(String[] args) {
        leftArray = new Integer[arrays.length >> 1];

        sort(0, arrays.length);

        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + "_");
        }
    }

    private static void sort(int begin, int end) {
        if (end - begin < 2) return;
        int mid = (begin + end) >> 1;
        sort(begin, mid);
        sort(mid, end);
        merge(begin, end, mid);
    }

    private static void merge(int begin, int end, int mid) {
        int li = 0, le = mid - begin;
        int ri = mid, re = end;
        int ai = begin;

        //备份左边数组
        for (int i = li; i < le; i++) {
            leftArray[i] = arrays[begin + i];
        }
        //判断大小
        while (li < le) {
            if (ri < re && arrays[ri] < leftArray[li]) {
                arrays[ai++] = arrays[ri++];
            } else {
                arrays[ai++] = leftArray[li++];
            }
        }
    }


}
